package com.captjack.math;

/**
 * @author Jack Sparrow
 * @version 1.0.0
 * @date 2022/10/17 21:06
 * package com.captjack.math
 */
public class BinarySearch {

    public static int bsLeft(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int mid = low + high >>> 1;
            if (arr[mid] >= target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        if (low > arr.length - 1) {
            return -1;
        }
        return arr[low] == target ? low : -1;
    }

    public static int bsRight(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int mid = low + high >>> 1;
            if (arr[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        if (high < 0) {
            return -1;
        }
        return arr[high] == target ? high : -1;
    }

}
